half-full enumeration

Example 1

I have a sequence of 4 numbers of length N=4000. We want to count the combinations where the elements are selected one by one and the sum is zero.

If you naively search the whole area, you will not make it in 4000^4.

Preprocessing: Enumerate the sum of all combinations in 4000^2 for the two sequences of numbers. Let X denote this.

The whole search is done in 4000^2 for the remaining two sequences. The sum of the two values is s.

Find the -s from X.

Example 2

question (e.g. on a test)

Select some from a set of size N=40

The elements of the set are goods of weight wi, value vi

The weight of the selected item must not exceed W

Maximize the sum of your values.

w and v can take values up to 10^15

2^40 is too big to search all of them; 2^20 can enumerate them all. Let X denote this.

Do a full search in 2^20 for the other half. If the sum of the weights is w, then the problem is to find the largest v from X whose weight does not exceed w-w.

2^(N/2)N as a whole

When the range of values is small, O(NW) can be calculated by DP using the "Weight→Value" table.

---